package learn.recursion;

import org.jetbrains.annotations.NotNull;


/**
 * @author baoshi
 */
public class MiGong {
    public static void main(String[] args) {
        //建立一个迷宫的基础
        int[][] map = new int[8][7]; //迷宫的基础大小为8行7列
        //设置墙
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;//第1行设置为墙
            map[7][i] = 1;//第8行设置为墙
        }
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;//第1列设置为墙
            map[i][6] = 1;//第7列设置为墙
        }
        map[3][1] = 1;
        map[3][2] = 1;
        setWay(map, 1, 1);
        printMap(map);
    }

    /**
     * 如果走到（6,5）游戏通过
     * 约定当map[i][j]=[0] 表示没有走过这个格子，[2]表示可以走，[3]表示走过了但是走不通
     * 约定下->右->上->左，如果该点走不通，再回溯
     * i j 作为输入的坐标，依次尝试在下右上左四个方向上进行尝试，
     * 如果哪个尝试成功了，就走到那个点上，再次尝试走一步，直到走到6,5点
     * 如果尝试失败了，将此点标记为不可通过点，然后回溯到上一个点，尝试走其他的策略
     * 如果其他策略也都无法通过，则将此点也标记为不可通过点，回溯到上一点，进行尝试
     * 直至回溯到可以通过的位置
     * 如果无法找到可以通过的点，那么将一直回溯到起点，此时方法也会结束
     *
     * @param map 地图
     * @param i   开始位置的纵坐标
     * @param j   开始位置的横坐标
     * @return 是否找到路
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if (map[6][5] == 2) { //终点到达，游戏结束
            return true;
        }
        int cur = map[i][j];
        if (cur == 0) {//该点没有走过
            map[i][j] = 2;//走到该点
            return strategy1(map, i, j);
        } else {
            /*
              当前点不为0
              1. 其可能为1 墙，走不了
              2. 2 走过了，不能走回头路，不用尝试了。因为如果四个方向都走不通，会回溯到这个点的
              3. 3 走过了。但是不通
              这几种情况说明次点无法通向终点，应该选择其他方向
             */
            return false;
        }
    }

    /**
     * 策略1 下 右 上 左
     * @param map 迷宫
     * @param i   纵坐标
     * @param j   横坐标
     * @return 是不是通路
     */
    private static boolean strategy1(int[][] map, int i, int j) {
        if (setWay(map, i + 1, j)) {//向下走一格
            return true;
        } else if (setWay(map, i, j + 1)) {//向右走一格
            return true;
        } else if (setWay(map, i - 1, j)) {//向上走一格
            return true;
        } else if (setWay(map, i, j - 1)) {//向左走一格
            return true;
        } else {//四个方向都做不通，表示该点为死点，走不通
            map[i][j] = 3;//表示走过了但是走不通
            return false;
        }
    }

    /**
     * 策略2 上右下左
     *
     * @param map 迷宫
     * @param i   纵坐标
     * @param j   横坐标
     * @return 是不是通路
     */
    private static boolean strategy2(int[][] map, int i, int j) {
        if (setWay(map, i - 1, j)) {//向上走一格
            return true;
        } else if (setWay(map, i, j + 1)) {//向右走一格
            return true;
        } else if (setWay(map, i + 1, j)) {//向下走一格
            return true;
        } else if (setWay(map, i, j - 1)) {//向左走一格
            return true;
        } else {//四个方向都做不通，表示该点为死点，走不通
            map[i][j] = 3;//表示走过了但是走不通
            return false;
        }
    }

    private static void printMap(@NotNull int[][] map) {
        for (int[] ints : map) {
            for (int i : ints) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
}
